#!/usr/bin/python

import math;
from eulerlib import number;

nlimit=1000000;

def genprimelist(limit):
	sieve=[0]*(limit+1);
	for x in range(2,int(math.sqrt(limit))+1):
		if(sieve[x]==1):
			continue;
		y=x+x;
		while y<=limit:
			sieve[y]=1;
			y+=x;

	out=[];
	for i in xrange(2,limit+1):
		if sieve[i]==0:
			out.append(i);

	return out;		

primeslist=genprimelist( int(math.sqrt(nlimit))+1);
def totient(n):
	if number.is_prime(n):
		return n-1;

	bound=int(math.sqrt(n))+1;
	totient=n;
	for p in primeslist:
		if p>bound:
			break;
		if n%p==0:
			totient*=(1-1.0/p);
	return int(totient);



def euler69():
	sqrtnlimit=int(math.sqrt(nlimit))+1;
	"""
	totient=[1]*(nlimit+1);

	for x in xrange(2,sqrtnlimit):
		y=x;
		while y<nlimit:
			for i in xrange(x):
				y+=1;
				if(y>nlimit):
					break;
				totient[y]+=1;
			y+=1;
	"""
	maxratio=0.0;
	maxn=0;
	for n in xrange(2,nlimit+1):
		if( n >6 and  (n/math.sqrt(n))<maxratio):
			continue;

		totientn=totient(n);
		if( float(n)/totientn > maxratio):
			maxn=n;
			maxratio=float(n)/totientn;
			print "new max: %d with ratio %f" % (maxn, maxratio);

	return maxn;

#faster euler69: (from euler72)

def euler69():
	sieve=range(nlimit+1);
	
	sieve[1]=0;

	maxratio=0.0;
	maxn=0;

	for x in xrange(2,nlimit):
		if sieve[x]==x:# x is prime
			sieve[x]=x-1.0;
			mult=(1.0-1.0/x);
			y=x+x;
			while(y<=nlimit):
				sieve[y]*=mult;
				y+=x;
		if( float(x)/sieve[x]>maxratio):
			maxratio=float(x)/sieve[x];
			maxn=x;
	return maxn;



print euler69();
	
